package william.bit;

/**
 * @author ZhangShenao
 * @date 2024/2/21
 * @description <a href="https://leetcode.cn/problems/counting-bits/description/">...</a>
 */
public class Leetcode338_比特位计数 {
    /**
     * 利用奇偶性解决
     * 奇数的最后一位一定是1 偶数的最后一位一定是0
     * 如果一个数是奇数,那么它包含的1的个数=它前一个偶数包含的1的个数+1
     * 如果一个数是偶数,那么它包含的1的个数=它除以2(右移一位)的数中包含1的个数,因为偶数的右移不会改变1的个数
     */
    public int[] countBits(int n) {
        //边界条件校验
        if (n < 0) {
            return new int[0];
        }

        //首先记录0中1的个数
        int[] res = new int[n + 1];
        res[0] = 0;

        for (int i = 1; i <= n; i++) {
            if ((i & 1) == 0) {    //偶数中1的个数=它右移一位的数中1的个数
                res[i] = res[i >> 1];
            } else { //奇数中1的个数=它前一个偶数中1的个数+1
                res[i] = res[i - 1] + 1;
            }
        }

        //返回结果
        return res;
    }
}
